#include <iostream>
#include <vector>
using namespace std;

class Solution {
	int max_coins(vector<int> &nums, int l, int r, vector<vector<int>> &dp)
	{
                if(dp[l][r] != -1){
                        return dp[l][r];
                }
		if (l == r) {
			return dp[l][r] = nums[l - 1] * nums[l] * nums[r + 1];
		}
		int ans = 0;
		for (int p = l; p <= r; p++) {
			int coins = nums[p] * nums[l - 1] * nums[r + 1];
			coins += max_coins(nums, l, p - 1, dp);
			coins += max_coins(nums, p + 1, r, dp);
			ans = max(ans, coins);
		}
		return dp[l][r] = ans;
	}

        int max_coins(vector<int> &nums)
        {
                int n = nums.size();
                vector<vector<int>> dp(n, vector<int>(n, 0));

                // for(int i = 1; i < n - 1; i++){
                //         dp[i][i] = nums[i + 1] * nums[i] * nums[i -1];
                // }

                for(int col = 1; col < n - 1; col ++){
                        for(int l = 1, r = col; r < n - 1; l++, r++){
                                for(int p = l; p <= r; p++){
                                        dp[l][r] = max(dp[l][r], nums[p] * nums[l - 1] * nums[r + 1] + dp[l][p - 1] + dp[p + 1][r]);
                                }
                        }
                }

                return dp[1][n - 2];
        }

    public:
	int maxCoins(vector<int> &nums)
	{
		nums.insert(nums.begin(), 1);
		nums.insert(nums.end(), 1);
                int n = nums.size();
                // vector<vector<int>> dp(n, vector<int>(n, -1));
		// return max_coins(nums, 1, nums.size() - 2, dp);
                return max_coins(nums);
	}
};

int main()
{
	vector<int> nums = { 3, 1, 5, 8 };
	cout << Solution().maxCoins(nums) << endl;
	return 0;
}